1. Field
The present invention relates generally to network security and, more specifically, to methods and apparatuses for performing Montgomery multiplications.
2. Description
Public key cryptography is a part of key exchange/connection setup protocols such as the Internet Key Exchange protocol (IKE) (used in IP security protocol (IPSEC)) and the Secure Sockets Layer protocol (SSL). Public key security schemes such as Diffie-Hellman key exchange, Rivest Shamir Adleman (RSA) ciphering, RSA digital signature, and digital signature authority (DSA) are commonly used for this purpose. Public key security schemes are known to be very computationally intensive. The computation that is at the heart of most public key security schemes is modular exponentiation with very large numbers. 512 bit and 1024 bit numbers (keys) are normally used these days and there is a desire to increase the key size. It is very likely that the size of the operands of the modular exponentiation operation will increase to 2048 and 4096 bit numbers and beyond in the near future. The Montgomery multiplication is a commonly used method for performing the modular exponentiation operations. In order to perform key exchange/connection setup at the rates required in today's networks, specialized modular exponentiation hardware is required. When the Montgomery multiplication is used, the specialized modular exponentiation hardware mainly comprises one or more Montgomery multiplication engines. The speed of the Montgomery multiplication engines affects the speed of performing key exchange/connection setup in network communications. Therefore, it is desirable to improve the efficiency of a Montgomery multiplication engine.